package com.fyl.leetcode.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author:fyl
 * @date 2021/5/23 15:56
 * @Modified By:
 * @Modified Date:
 * @Description:
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 * 说明: 叶子节点是指没有子节点的节点。
 *    1
 *  /   \
 * 2     3
 *  \
 *   5
 * 输出: ["1->2->5", "1->3"]
 * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 */
public class BinaryTreePaths {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<String> list = new ArrayList<>();
        findPaths(root,"",list);
        return list;
    }

    private void findPaths(TreeNode root, String cur, List<String> list) {
        if (root == null) {
            return;
        }
        cur += root.val;
        //叶子节点的判断条件
        if (root.left == null && root.right == null) {
            list.add(cur); //将叶子节点加入路径
        } else {
            findPaths(root.left, cur + "->", list);
            findPaths(root.right, cur + "->", list);
        }

    }
}
